package Beginner_Algorithm;


public class Single_linked_list_in_reverse_order {

    public static class Node {
        int num;
        Node next;

        public Node(int num) {
            this.num = num;
        }
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = null;
        Node head = node1;
        print(head);
        head = reverseKGroup(head,3);
        print(head);
    }

    //逆序部分
    public static void reverse(Node start, Node end) {
        end = end.next;
        Node cur = start;
        Node next = null;
        Node pre = null;
        while (cur != end) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        start.next = end;
    }

    public static Node reverseKGroup(Node head,int k) {
        Node start = head;
        Node end = getKGroupEnd(head, k);
        if (end == null) {
            return head;
        }
        head = end;
        reverse(start,end);
        Node ls = start;
        while(ls.next != null) {
            start = ls.next;
            end = getKGroupEnd(start,k);
            if(end == null) {
                return head;
            }
            reverse(start,end);
            ls.next = end;
            ls = start;
        }
        return head;
    }


    //给start位置和k,给出end
    public static Node getKGroupEnd(Node start, int k) {
        while (--k != 0 && start != null) {
            start = start.next;
        }
        return start;
    }

    //逆序整个链表
    public static Node change(Node head) {
        Node next = null;
        Node pre = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    //打印整个链表
    private static void print(Node head) {
        while (head != null) {
            System.out.println(head.num);
            head = head.next;
        }
    }
}
